Я послушал ваши отзывы и комментарии по поводу моего небольшого проекта. Реализовал некоторые из высказанных идей и, конечно, добавил к ним часть своих.
Самое главное, самое сложное и самое незаметное: поменялся алгоритм поиска. Вместо точного и медленного метода ветвей и границ теперь почти точный и метаэвристичекий метод муравьиной колонии. В основе проекта лежит Travelling Salesman Problem (Задача коммивояжёра), которая является NP-полной. А это означает, что нет другого пути решения её, кроме как перебрать все варианты. Количество вариантов можно посчитать по формуле \(n! \over 2\), где \(n\) — количество промежуточных городов. Если подставить в эту формулу, например, 15 получим 653 837 184 000 вариантов, а это уже очень много. Поэтому пришлось воспользоваться приближенным алгоритмом, который работает быстро, но и решение выдаёт не всегда оптимальное. Кстати, так как внутри алгоритма задействован генератор случайных чисел, решение может меняться от запуска к запуску, достаточно нажать кнопку обновить.
Я убрал из проекта AngularDart, что позволило уменьшить размер JavaScript-файла в 3 раза.
Теперь можно скопировать ссылку с маршрутом и отправить кому-нибудь. Только осторожно, чем больше городов будет в маршруте, тем длиннее будет ссылка и некоторые браузеры могут не справиться с такой длиной. Вот вам, например, ссылка на маршрут по всем европейским столицам.
Упростилось добавление городов в маршрут. Из вариантов объектов теперь убираются лишние, если вариант только один, то он добавляется автоматически. И самое главное: можно добавлять города, даже не прикасаясь к мышке, используя для выбора варианта клавиши «Вверх», «Вниз» и «Enter».
А ещё теперь можно развернуть карту на весь экран, чтобы было удобнее её изучать.
Исправлены ошибки.
Прошу любить и жаловать. Замеченные недочёты можно описывать в комментариях к этому посту, ну или присылать любым другим способом.
Поделюсь некоторыми сложностями, с которыми я столкнулся, запуская планировщик маршрута.
Конечно, во время самой разработки все сложности сводились к алгоритмическим. В Dartium всё работало как положено с нужным количеством ошибок и предупреждений. Проблемы начались сразу после компиляции в JavaScript и запуске в обычном браузере (кто бы сомневался). Проект не запустился, выдав странного вида stack trace. Ну что же, пересобираем проект без минификации. Stack trace стал читаемым, ошибки понятными. Как оказалось, вся проблема была в аннотации @MirrorsUsed. Дело в том, что mirrors (так называется reflection в Dart) занимает непозволительно много места в скомпилированном коде. И для того, чтобы этого избежать, авторы Dart предлагают использовать эту аннотацию для указания библиотек и классов, информацию о которых нужно будет получить во время исполнения (кстати, в будущем обещают доработать компилятор, что избавит от необходимости использовать эту аннотацию). Так вот, мой класс контроллера не был указан в @MirrorsUsed и, соответственно, AngularDart не мог с ним работать.
Исправил, скомпилировал, не запустилось. Правда, в этот раз я увидел несколько больше, чем просто пустую страницу. Немного поисков — и обнаружилась вторая проблема: нельзя в шаблонах AngularDart использовать методы встроенных объектов Dart. То есть в Dart можно, а в JavaScript нельзя. Конкретно в моем случае было написано:
{{segment[0].distanceTo(segment[1]).round()}}Понятное дело, JavaScript и не догадывается о методе round у типа double. Да, собственно, про существование double он тоже не догадывается. Поэтому нужно писать геттер или вспомогательную функцию. Например так:
{{segment[0].distanceToRound(segment[1])}}Ура, запустилось! Теперь осталось собрать минифицированную версию и выложить. Но после сборки проект снова упал с непонятным stack trace, как и в самом начале.
Не один час был потрачен на гугление всевозможных причин. Дело почти дошло до того, чтобы написать новый багрепорт о неправильной компиляции. Но я вовремя остановился, и хорошо, потому что ошибка была у меня и, кстати, довольна простая: я пытался проинициализировать Яндекс.Карты, а функция-конструктор не существовала. Вот проблемная строка, она соответствует map = new ymaps.Map(“map”, options); в JavaScript:
map = new JsObject(context['ymaps']['Map'], ["map", options]);Но ведь несжатая версия работает! Моё предположение, что сжатая версия приложения инициализируется значительно быстрее и поэтому API Яндекс.Карт ещё не готово к тому времени, оказалось верным, и вызов функции ymaps.ready всё исправил.
Итог. Более-менее сложное Dart-приложение хорошо работает в браузерах без поддержки Dart. Но зато когда сталкиваешься с проблемой, которая возникает только в скомпилированном и минифицированном коде, можно потратить довольно много времени на поиск решения просто потому, что подсказок никто не даст, а код выглядит довольно запутанно. Но в своей практике я сталкивался со случаями, когда и обычное JavaScript-приложение после сжатия начинало вести себя неправильно и возникали те же проблемы поиска решения.
Хочется отметить минификатор JS, встроенный в Dart. Он заменяет все ; на переводы строк. Из-за этого в результате получается файл со множеством строк, а не с одной, как в случае с другими минификаторами. А это, в свою очередь, сильно упрощает ручной анализ кода.
Здравствуйте, дорогие читатели!
За окном вовсю сияет март, а мы уже начали готовиться к новому большому летнему путешествию (обязательно посмотрите предыдущее, если, конечно, ещё не видели его). К сожалению, идея проехать Соединённые Штаты поперёк накрылась медным тазом отложена до лучших времён. Но это не причина для уныния, ведь есть ещё сотни стран, требующих нашего внимания. И мы решили не заморачиваться и повторить прошлогодний опыт бэкпэкерства с InterRail, благо пол-Европы осталось неизъезженной.
Сказано — сделано. Набросали списочек городов для посещения и оказалось, что маршрут, в отличие от предыдущего года, не очевиден. В каком порядке их нужно объезжать, чтобы расстояние, преодолённое на поезде, получилось минимальным? Поиск нужных сервисов для составления маршрутов ничего не дал, а значит нужно написать свой! Что я и сделал.
Представляю вам планировщик маршрутов. Сервис довольно простой: вводишь начальный город, конечный, а также список городов посередине, — и получаешь оптимальный маршрут. Расстояния между городами считаются по прямой, поэтому результат оптимален только для самолётов. А для остального транспорта стоит учитывать, что дороги кривые и ездят по ним с разной скоростью. Но для того, чтобы прикинуть маршрут, информации достаточно. Конечно, между некоторыми пунктами дороги может вообще не существовать, но не беда: любой отрезок из пути можно исключить и система выдаст другой маршрут с учётом этого ограничения.
Для приготовления сервиса мне понадобились: Яндекс.Карты, AngularDart, Bootstrap. Туда пришлось добавить немного логики и свободного времени. Всё это было смешано, взболтано, вылито в высокий бокал и украшено методом ветвей и границ, прямо как учили в универе. Приятного аппетита.
Прошу опробовать и написать свои замечания и пожелания в комментариях. Исходники всего это дела можно увидеть всё там же — на GitHub.
Всегда к вашим услугам,
Редакция блога.